package org.example.struct.array;

import java.util.Arrays;

/**
 * @author liyishan
 * @date 2023/8/9 11:37
 * @apiNote
 */

public class Test00849MaxDistToClosest {
    public static void main(String[] args) {
        int[] seats = new int[]{1, 0, 0, 0, 1, 0, 1};
        System.out.println(test(seats));
    }

    public static int test(int[] seats) {
        int N = seats.length;
        int[] left = new int[N], right = new int[N];
        Arrays.fill(left, N);
        Arrays.fill(right, N);

        for (int i = 0; i < N; ++i) {
            if (seats[i] == 1) {
                left[i] = 0;
            } else if (i > 0) {
                left[i] = left[i-1] + 1;
            }
        }

        for (int i = N-1; i >= 0; --i) {
            if (seats[i] == 1) {
                right[i] = 0;
            } else if (i < N-1) {
                right[i] = right[i+1] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            if (seats[i] == 0) {
                ans = Math.max(ans, Math.min(left[i], right[i]));
            }
        }
        return ans;
    }

    public static int test1(int[] seats){
        int N = seats.length;
        int prev = -1, future = 0;
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            if (seats[i] == 1) {
                prev = i;
            } else {
                while (future < N && seats[future] == 0 || future < i) {
                    future++;
                }
                int left = prev == -1 ? N : i - prev;
                int right = future == N ? N : future - i;
                ans = Math.max(ans, Math.min(left, right));
            }
        }

        return ans;
    }

    public static int test2(int[] seats) {
        int N = seats.length;
        int K = 0; //current longest group of empty seats
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            if (seats[i] == 1) {
                K = 0;
            } else {
                K++;
                ans = Math.max(ans, (K + 1) / 2);
            }
        }

        for (int i = 0; i < N; ++i) {
            if (seats[i] == 1) {
                ans = Math.max(ans, i);
                break;
            }
        }

        for (int i = N-1; i >= 0; --i) {
            if (seats[i] == 1) {
                ans = Math.max(ans, N - 1 - i);
                break;
            }
        }

        return ans;
    }
}
